package com.LeeCode;

/**
 * 二叉树中的伪回文路径
 */

public class Code1457 {
    public static void main(String[] args) {
        Integer[] arr = {2, 3, 1, 3, 1, null, 1};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1457().pseudoPalindromicPaths(root));
    }

    public int pseudoPalindromicPaths(TreeNode root) {
        int[] cnt = new int[9];
        return dfs(root, cnt);
    }

    private int dfs(TreeNode root, int[] cnt) {
        if (root == null) return 0;
        cnt[root.val - 1]++;
        if (root.left == null && root.right == null) {
            int count = 0;
            for (int i = 0; i < cnt.length; i++) {
                count += (cnt[i] & 1) == 1 ? 1 : 0;
            }
            cnt[root.val - 1]--;
            return count < 2 ? 1 : 0;
        }
        int left = dfs(root.left, cnt);
        int right = dfs(root.right, cnt);
        cnt[root.val - 1]--;
        return left + right;
    }
}
